package com.xixi;

import java.util.HashMap;
import java.util.Map;

public class CodeTest {


    int maxPointSum = 2;
    int[] res = new int[2];

    public int[] bestLine(int[][] points) {
        int n = points.length;
        if (n == 2) return new int[]{0, 1};


        Map<Double, Integer>[] slopeMap = new HashMap[n];
        for (int i = n - 1; i >= 0; i--) {

            slopeMap[i] = new HashMap<>();

            int xA = points[i][0];
            int yA = points[i][1];
            for (int j = n - 1; j > i; j--) { //B → A , A → B are in same line, so don't have to recal them;
                int xB = points[j][0];
                int yB = points[j][1];

                int dx = xA - xB;
                int dy = yA - yB;

                double m = dy == 0 ? Double.POSITIVE_INFINITY : dx == 0 ? 0 : (double) dx / dy;

                int count = slopeMap[j].getOrDefault(m, 1) + 1;

                slopeMap[i].put(m, count);

                if (count >= maxPointSum) {
                    maxPointSum = count;
                    res[0] = i;
                    res[1] = j;
                }

            }


        }


        return res;

    }

    public static void main(String[] args) {

        int[][] points = new int[][]{{-13260, 8589}, {1350, 8721}, {-37222, -19547}, {-54293, -29302}, {-10489, -13241}, {-19382, 574}, {5561, 1033}, {-22508, -13241}, {-1542, 20695}, {9277, 2820}, {-32081, 16145}, {-50902, 23701}, {-8636, 19504}, {-17042, -28765}, {-27132, -24156}, {-48323, -4607}, {30279, 29922}};

        CodeTest cod = new CodeTest();
        int[] res = cod.bestLine(points);
        System.out.println(res[0] + "," + res[1]);
    }



}
